package com.kavin.collection.datastructure;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName BinarySearch
 * @Description
 * @Author kavin
 * @Date 2022/8/15 15:46
 * @Version 1.0
 */
public class BinarySearch {


    @Test
    public void insertTree(){
        TreeNode node = new TreeNode(5,null,null);
        for(int i = 0 ; i < 10; i ++){
            if(i ==5){
                continue;
            }
            TreeNode temp = new Solution().insertIntoBST(node,i);
            node = temp;
        }
    }



    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {

        //创建一个类型为TreeNode 的队列， 另外创建一个类型为Integer的ArrayList用于存放结果
        Queue<TreeNode> q = new LinkedList<>();
        ArrayList<Integer> res = new ArrayList<> ();

        if(root == null) return res; // 注意此处的res是一个空数组

        q.offer(root); // q.offer() 是队列的一个方法，表示向队列尾部添加元素


        while(! q.isEmpty()) {
            TreeNode cur = q.poll(); // q.poll()表示从队列头部删除数据
            res.add(cur.val);        // q.add() 也是队列的一个方法，表示向队列尾部添加元素

            if(cur.left != null) {q.offer(cur.left);}
            if(cur.right != null) {q.offer(cur.right);}


        }
        return res;
    }


    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }



    class Solution {
        /*
            二叉树插入原理:
            1.前序插入(根左右) 如果插入的树大于根,数则往右侧移动,与右侧分支的根进行比较，然后重复前面的操作
            */
        public TreeNode insertIntoBST(TreeNode root, int val) {
            //当传入的根节点为空,则将传入的值设置为节点
            if (root == null){
                //如果tree为空的,那么就创建一个新的二叉并赋值
                return new TreeNode(val);
            }

            if (root.val<val){
                //当当前的值是大于左侧的值，则往右侧移动
                root.right=insertIntoBST(root.right,val);
            }else{
                //反之
                root.left=insertIntoBST(root.left,val);
            }
            return root;
        }


        //解法2：循环判断
        public TreeNode insertIntoBST2(TreeNode root, int val) {
            if (root == null){
                return new TreeNode(val);
            }
            TreeNode parent=root,p=root;
            while(true){
                if (p!=null){
                    parent = p; //记录上个节点
                    p = p.val>val?p.left:p.right;
                }else{
                    //当p为null了,则已经找到位置了,现在则需要将值进行插入
                    if (parent.val>val){
                        parent.left = new TreeNode(val);
                    }else{
                        parent.right = new TreeNode(val);
                    }
                    break;
                }

            }
            return root;
        }
        //解法三:循环遍历,

        /**
         *
         * @param root
         * @param val
         * @return
         *
         * 解法思路：我们先通过一个循环找到能插入位置的父节点，
         * 然后我们就对值与父节点的值进行比较,如果该值小于父节点的话我们就插入在父节点的左侧
         */
        public TreeNode insertBST3(TreeNode root,int val){
            if (root == null){
                return new TreeNode(val);
            }
            //定义一个父级二叉树 用来记录上个操作的节点
            TreeNode parent =root,p=root;
            while(p!=null){
                //如果p部位空的话,就和val比较来进行节点的移动
                parent = p; //记录上一个节点,用于最后的链接
                p = p.val<val?p.right:p.left;//节点进行移动。
            }
            if(parent.val>val){
                //如果父级的val是大于输入的val，那么插在左边
                parent.left = new TreeNode(val);
            }else{
                //否则插在右边
                parent.right = new TreeNode(val);
            }

            return root;
        }


    }





    /**
     * @Author kavin
     * @Description 二分查找法
     * @Param [arr, searchValue]
     * @return
     **/
    public static  int BinarySearchMethod(int[] arr,int searchValue) {
        int left = 0 ,right=arr.length-1,m;
        while (true){


            m = (left + right) /2;

            if(left > right){
                return -1;
            }
            if(arr[m] == searchValue){
                return  m;
            }else if(arr[m] > searchValue){
                right = m -1;
            }else{
                left = m +1;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,3,4,6,23,45,67,78,89,90,100};  //有序的集合
        System.out.println(BinarySearchMethod(arr,670));
    }

}
